1. Technical Field
The present disclosure generally relates to computer systems. More specifically, this disclosure relates to optimizing bounds checking using computer algebra.
2. Related Art
Programming languages often use constructs which are indexed by a value. For example, most programming languages include an array construct which stores a sequence of elements that can be accessed by using an index value.
Note that the index value is valid only when it is within a specified range of values. If a system accesses an element using an index value that is outside the valid range, the system can malfunction. Specifically, using an invalid index value to read an element will return garbage, and using an invalid index value to write an element can corrupt memory.
Note that the problem of bounds checking is not limited to arrays or other indexed data structures. In general, to ensure that a piece of code executes correctly, we may need to ensure that certain variables, parameters, and/or arguments are within a range of values. For example, a function may generate correct results only if the function's arguments fall within a certain range of values.
Bounds-checking instructions can be added to a piece of code to ensure that variables, parameters, and/or arguments do not violate their respective bounds during runtime. Unfortunately, bounds-checking instructions can significantly increase the runtime overhead. For example, if the bounds-checking instructions are executed each time a loop variable is incremented, it can significantly increase runtime.
Hence, what is needed are techniques and systems for optimizing bounds checking